home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / ohlfind.zip / FASTFIND.C < prev    next >
C/C++ Source or Header  |  1990-06-25  |  5KB  |  197 lines
  1. /* fastfind.c -- list files in database matching a pattern
  2.  
  3.    'fastfind' scans a file list for the full pathname of a file
  4.    given only a piece of the name.  The list has been processed with
  5.    "front-compression" and bigram coding.  Front compression reduces
  6.    space by a factor of 4-5, bigram coding by a further 20-25%.
  7.  
  8.    The codes are:
  9.  
  10.    0-28        likeliest differential counts + offset to make nonnegative
  11.    30        escape code for out-of-range count to follow in next word
  12.    128-255     bigram codes (128 most common, as determined by 'updatedb')
  13.    32-127      single character (printable) ASCII residue
  14.  
  15.    A novel two-tiered string search technique is employed:
  16.  
  17.    First, a metacharacter-free subpattern and partial pathname is
  18.    matched BACKWARDS to avoid full expansion of the pathname list.
  19.    The time savings is 40-50% over forward matching, which cannot efficiently
  20.    handle overlapped search patterns and compressed path residue.
  21.  
  22.    Then, the actual shell glob-style regular expression (if in this form)
  23.    is matched against the candidate pathnames using the slower routines
  24.    provided in the standard 'find'.
  25.  
  26.    Author: James A. Woods (jaw@riacs.edu)
  27.    Modified by David MacKenzie (djm@ai.mit.edu)
  28.    Public domain. */
  29.  
  30. #include <stdio.h>
  31. #ifndef USG
  32. #include <strings.h>
  33. #else
  34. #include <string.h>
  35. #define index strchr
  36. #define rindex strrchr
  37. #endif
  38. #include <sys/types.h>
  39. #include <sys/param.h>
  40.  
  41. #ifndef MAXPATHLEN
  42. #define MAXPATHLEN 1024
  43. #endif
  44.  
  45. #define    YES    1
  46. #define    NO    0
  47.  
  48. #define    OFFSET    14
  49.  
  50. #define    ESCCODE    30
  51.  
  52. extern int errno;
  53.  
  54. char *index ();
  55. char *patprep ();
  56. void error ();
  57.  
  58. void
  59. fastfind (pathpart)
  60.      char *pathpart;
  61. {
  62.   register char *p, *s;
  63.   register int c;
  64.   char *q;
  65.   int i, count = 0, globflag;
  66.   FILE *fp;
  67.   char *patend, *cutoff;
  68.   char path[MAXPATHLEN];
  69.   char bigram1[128], bigram2[128];
  70.   int found = NO;
  71.  
  72.   fp = fopen (FCODES, "r");
  73.   if (fp == NULL)
  74.     error (1, errno, "%s", FCODES);
  75.  
  76.   for (i = 0; i < 128; i++)
  77.     {
  78.       bigram1[i] = getc (fp);
  79.       bigram2[i] = getc (fp);
  80.     }
  81.  
  82.   globflag = glob_pattern_p (pathpart);
  83.   patend = patprep (pathpart);
  84.  
  85.   c = getc (fp);
  86.   for (;;)
  87.     {
  88.       count += ((c == ESCCODE) ? getw (fp) : c) - OFFSET;
  89.  
  90.       for (p = path + count; (c = getc (fp)) > ESCCODE;)
  91.     /* Overlay old path. */
  92.     if (c < 0200)
  93.       *p++ = c;
  94.     else
  95.       {
  96.         /* Bigrams are parity-marked. */
  97.         *p++ = bigram1[c & 0177];
  98.         *p++ = bigram2[c & 0177];
  99.       }
  100.       if (c == EOF)
  101.     break;
  102.       *p-- = '\0';
  103.       cutoff = path;
  104.       if (!found)
  105.     cutoff += count;
  106.  
  107.       for (found = NO, s = p; s >= cutoff; s--)
  108.     if (*s == *patend)
  109.       {
  110.         /* Fast first char check. */
  111.         for (p = patend - 1, q = s - 1; *p != '\0'; p--, q--)
  112.           if (*q != *p)
  113.         break;
  114.         if (*p == '\0')
  115.           {
  116.         /* Success on fast match. */
  117.         found = YES;
  118.         if (globflag == NO || glob_match (pathpart, path, 1))
  119.           puts (path);
  120.         break;
  121.           }
  122.       }
  123.     }
  124. }
  125.  
  126. static char globfree[100];
  127.  
  128. /* Extract the last glob-free subpattern in NAME for fast pre-match;
  129.    prepend '\0' for backwards match; return the end of the new pattern. */
  130.  
  131. char *
  132. patprep (name)
  133.      char *name;
  134. {
  135.   register char *p, *endmark;
  136.   register char *subp = globfree;
  137.  
  138.   *subp++ = '\0';
  139.   p = name + strlen (name) - 1;
  140.   /* Skip trailing metacharacters (and [] ranges). */
  141.   for (; p >= name; p--)
  142.     if (index ("*?", *p) == 0)
  143.       break;
  144.   if (p < name)
  145.     p = name;
  146.   if (*p == ']')
  147.     for (p--; p >= name; p--)
  148.       if (*p == '[')
  149.     {
  150.       p--;
  151.       break;
  152.     }
  153.   if (p < name)
  154.     p = name;
  155.   /* If pattern has only metacharacters,
  156.      check every path (force '/' search). */
  157.   if (p == name && index ("?*[]", *p) != 0)
  158.     *subp++ = '/';
  159.   else
  160.     {
  161.       for (endmark = p; p >= name; p--)
  162.     if (index ("]*?", *p) != 0)
  163.       break;
  164.       for (++p; p <= endmark && subp < (globfree + sizeof (globfree));)
  165.     *subp++ = *p++;
  166.     }
  167.   *subp-- = '\0';
  168.   return subp;
  169. }
  170.  
  171. /* The name this program was run with. */
  172. char *program_name;
  173.  
  174. /* Usage: find pattern
  175.    Searches a pre-computed file list constructed nightly by cron.
  176.    Its effect is similar to, but much faster than,
  177.    find / -mtime +0 -name "*pattern*" -print */
  178.  
  179. void
  180. main (argc, argv)
  181.      int argc;
  182.      char **argv;
  183. {
  184.   int optind;
  185.  
  186.   program_name = argv[0];
  187.  
  188.   if (argc == 1)
  189.     {
  190.       fprintf (stderr, "Usage: %s pattern...\n", argv[0]);
  191.       exit (1);
  192.     }
  193.   for (optind = 1; optind < argc; ++optind)
  194.     fastfind (argv[optind]);
  195.   exit (0);
  196. }
  197.